package com.shawn.datastructure.heap;

/**
 * Minimum Priority Queue It is a part of heap data structure A heap is a specific tree based data
 * structure in which all the nodes of tree are in a specific order. that is the children are
 * arranged in some respect of their parents, can either be greater or less than the parent. This
 * makes it a min priority queue or max priority queue.
 * <p>
 * <p>
 * Functions: insert, delete, peek, isEmpty, print, heapSort, sink
 */
public class MinPriorityQueue {

	private int[] heap;
	private int capacity;
	private int size;

	// calss the constructor and initializes the capacity
	MinPriorityQueue(int c) {
		this.capacity = c;
		this.size = 0;
		this.heap = new int[c + 1];
	}

	// inserts the key at the end and rearranges it
	// so that the binary heap is in appropriate order
	public void insert(int key) {
		if (this.isFull()) {
			return;
		}
		this.heap[this.size + 1] = key;
		int k = this.size + 1;
		while (k > 1) {
			if (this.heap[k] < this.heap[k / 2]) {
				int temp = this.heap[k];
				this.heap[k] = this.heap[k / 2];
				this.heap[k / 2] = temp;
			}
			k = k / 2;
		}
		this.size++;
	}

	// returns the highest priority value
	public int peek() {
		return this.heap[1];
	}

	// returns boolean value whether the heap is empty or not
	public boolean isEmpty() {
		if (0 == this.size) {
			return true;
		}
		return false;
	}

	// returns boolean value whether the heap is full or not
	public boolean isFull() {
		if (this.size == this.capacity) {
			return true;
		}
		return false;
	}

	// prints the heap
	public void print() {
		for (int i = 1; i <= this.capacity; i++) {
			System.out.print(this.heap[i] + " ");
		}
		System.out.println();
	}

	// heap sorting can be done by performing
	// delete function to the number of times of the size of the heap
	// it returns reverse sort because it is a min priority queue
	public void heapSort() {
		for (int i = 1; i < this.capacity; i++) {
			this.delete();
		}
	}

	// this function reorders the heap after every delete function
	private void sink() {
		int k = 1;
		while (2 * k <= this.size || 2 * k + 1 <= this.size) {
			int minIndex;
			if (this.heap[2 * k] >= this.heap[k]) {
				if (2 * k + 1 <= this.size && this.heap[2 * k + 1] >= this.heap[k]) {
					break;
				} else if (2 * k + 1 > this.size) {
					break;
				}
			}
			if (2 * k + 1 > this.size) {
				minIndex = this.heap[2 * k] < this.heap[k] ? 2 * k : k;
			} else {
				if (this.heap[k] > this.heap[2 * k] || this.heap[k] > this.heap[2 * k + 1]) {
					minIndex = this.heap[2 * k] < this.heap[2 * k + 1] ? 2 * k : 2 * k + 1;
				} else {
					minIndex = k;
				}
			}
			int temp = this.heap[k];
			this.heap[k] = this.heap[minIndex];
			this.heap[minIndex] = temp;
			k = minIndex;
		}
	}

	// deletes the highest priority value from the heap
	public int delete() {
		int min = this.heap[1];
		this.heap[1] = this.heap[this.size];
		this.heap[this.size] = min;
		this.size--;
		this.sink();
		return min;
	}

	public static void main(String[] args) {
		// testing
		MinPriorityQueue q = new MinPriorityQueue(8);
		q.insert(5);
		q.insert(2);
		q.insert(4);
		q.insert(1);
		q.insert(7);
		q.insert(6);
		q.insert(3);
		q.insert(8);
		q.print(); // [ 1, 2, 3, 5, 7, 6, 4, 8 ]
		q.heapSort();
		q.print(); // [ 8, 7, 6, 5, 4, 3, 2, 1 ]
	}
}